//You have a list arr of all integers in the range [1, n] sorted in a strictly i
//ncreasing order. Apply the following algorithm on arr: 
//
// 
// Starting from left to right, remove the first number and every other number a
//fterward until you reach the end of the list. 
// Repeat the previous step again, but this time from right to left, remove the 
//rightmost number and every other number from the remaining numbers. 
// Keep repeating the steps again, alternating left to right and right to left, 
//until a single number remains. 
// 
//
// Given the integer n, return the last number that remains in arr. 
//
// 
// Example 1: 
//
// 
//Input: n = 9
//Output: 6
//Explanation:
//arr = [1, 2,3, 4,5, 6,7, 8,9,10]
//arr = [2, 4,6, 8,10]
//arr = [ 4, 8]
//arr = [0, 2, 0, 0, 0, 6, 0, 0,0]
//arr = [6]
// 
//
// Example 2: 
//
// 
//Input: n = 1
//Output: 1
// 
//
// 
// Constraints: 
//
// 
// 1 <= n <= 109 
// 
// 👍 114 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

//Java：Elimination Game
class P390EliminationGame {
    public static void main(String[] args) {
        Solution solution = new P390EliminationGame().new Solution();
        // TO TEST
        Assert.assertEquals(solution.lastRemaining(1000000), 6);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int lastRemaining(int n) {
            if(n==0)
                return 0;

            //return n==1?1:2*(n/2-lastRemaining(n/2)+1);
            //思路只计算剩下的第一位数字
            int one=1;
            int cha=1;
            boolean lr=true;//从左到右
            boolean jiou=n%2==0?true:false;//奇数为1

            while(n!=1)
            {
                if(lr||jiou)//1,从左到右 2,从右到左,但要是奇数,此时结果的第一位数是之前的第二位数
                {
                    one=one+cha;//通过等差性质 将第二位数取代第一位数,

                }
                lr=!lr;//方向转换
                cha<<=1;//差值翻倍
                n>>=1;//长度减半
                jiou = n % 2 == 0 ? true : false;//更新奇偶


            }

            return one;
        }
        public int lastRemainingA(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = i + 1;
            }
            int len = n;
            int index = 0;
            int start = 1;
            while (len > 1) {
                if (index >= n) {
                    index = n - 1;
                    start = -2;
                }
                else if (index <= 0) {
                    index = 0;
                    start = 2;
                }
                if (arr[index] != 0) {
                    arr[index] = 0;
                    len--;
                    index += start;
                }else{
                    index += start / 2;
                }

            }
            return arr[index];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}